# -*- coding: utf-8 -*-

'''
merge.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Merge Sort"

Tempo de execução:
    Pior cenário O(n log(n)).

O algoritmo merge-sort é projetado com o recurso À técnica de
divisão e conquista.

O algoritmo merge sort segue de perto o paradigma da divisão e
conquista.
  Divisão divide-se a sequência A de n elementos em duas
       sub-sequências com n/2 elementos cada;
  Conquista ordenam-se as duas sub-sequências recursivamente
       usando o procedimento merge sort;
  Combinação agregam-se (merge) as duas sub-sequências de modo
       a produzir a sequência final ordenada.

A ordem de crescimento, no pior cenário, é dada por O(n log(n)).


Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    p = 0 #p: posição inicial
    r = 19 #r: posição final
    merge_sort(A, p, r)
    print "depois A:", A
    pass

antes A:  [10, 11, 12, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
depois A: [1, 2, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 13, 14, 15, 16, 17, 20, 21]
>>>

"""

import sys
import math

def merge(A, p, q, r):

    n = q - p + 1
    nn = r - q

    L = [0] * (n + 1)
    R = [0] * (nn + 1)

    for i in range (0, n):
        L[i] = A[p + i]
        pass

    for i in range (0, nn):
        R[i] = A[q + i + 1]
        pass

    L[n] = sys.maxint
    R[nn] = sys.maxint
    
    i = 0
    j = 0

    for k in range(p, r + 1, 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
            pass
        else:
            A[k] = R[j]
            j = j + 1
            pass
        pass
    pass



def mergeSort(A, p, r):

    if p < r:
        # q = (p + r) / 2
        # floor - the largest integer value less than or equal to x.
        q = int (math.floor(p + r) / 2.0)
        mergeSort(A, p, q)
        mergeSort(A, q + 1, r)
        merge(A, p, q, r)
        pass
    pass

        
        

def main():
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    p = 0 #p: posição inicial
    r = 19 #r: posição final
    mergeSort(A, p, r)
    print "depois A:", A
    pass


if __name__ == '__main__':
    main()




